
#include <assert.h>

#include "common/alloc.h"

#include "str_hash_table.h"


typedef unsigned int HashInt;

static inline HashInt hash_func(const char * src_str, size_t len)
{
    const unsigned char * str = (const unsigned char *)src_str;
    size_t n = len;
    HashInt h = 0;
    HashInt g;

    while (n--)
    {
        h = (h << 4) + *str++;
        if ((g = (h & 0xf0000000)) != 0)
        {
            h ^= g >> 23;
        }

        h &= ~g;
    }

    return h;
}


struct HashTableEntry
{
    struct HashTableEntry * next;
    size_t          len;
    char            str[1];
};


#define VECTOR_NS(name)             ht_##name
#define VECTOR_ELEMENT_TYPE         struct HashTableEntry *
#define VECTOR_XREALLOC             xrealloc
#define VECTOR_XFREE                xfree
#define VECTOR_PREALLOCATED_SIZE    32
#include <templates/vector.h>

/*
 * hash table size MUST BE power of 2
 */
#define IDS_HASH_TABLE_SIZE         (1024)

#define IDS_TOKEN_ARRAY_TABLE_SIZE  (4096)

struct HashTable
{
    struct HashTableEntry * array[IDS_HASH_TABLE_SIZE];

    // optional array of linked table entries
    ht_Vector allocated_entries;
};



bool hash_table_contains(struct HashTable * ht, const char * str, size_t len)
{
    HashInt hash = hash_func(str, len) & (IDS_HASH_TABLE_SIZE - 1);
    struct HashTableEntry * token = ht->array[hash];

    while (token != NULL)
    {
        if ((token->len == len) && (0 == memcmp(str, token->str, len)))
        {
            // token found
            break;
        }

        token = token->next;
    }

    return (token != NULL);
}


struct HashTableEntry * hash_table_add(struct HashTable * ht, const char * str, size_t len)
{
    HashInt hash = hash_func(str, len) & (IDS_HASH_TABLE_SIZE - 1);
    struct HashTableEntry * token = ht->array[hash];

    // find token
    while (NULL != token)
    {
        if ((token->len == len) && (0 == memcmp(str, token->str, len)))
        {
            // such a token already exists
            return token;
        }

        // go next
        token = token->next;
    }

    // create new token entry
    token = xmalloc(sizeof(struct HashTableEntry) + len);
    token->len = len;
    memcpy(token->str, str, len);

    // put token to the table
    token->next = ht->array[hash];
    ht->array[hash] = token;

    // add to the allocated entries table
    ht_vector_push_back(&ht->allocated_entries, token);

    return token;
}


struct HashTable * create_hash_table()
{
    struct HashTable * ht = xmalloc(sizeof(struct HashTable));
    memset(ht->array, 0, IDS_HASH_TABLE_SIZE * sizeof(struct HashTableEntry *));
    ht_vector_init(&ht->allocated_entries);
    return ht;
}

void free_hash_table(struct HashTable * ht)
{
    size_t i;
    const size_t entries_count = ht_vector_size(&ht->allocated_entries);
    struct HashTableEntry ** entries = ht_vector_data(&ht->allocated_entries);

    for (i = 0; i < entries_count; ++i)
    {
        struct HashTableEntry * token = entries[i];
        xfree(token);
    }

    ht_vector_uninit(&ht->allocated_entries);
    xfree(ht);
}
